/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/ugly-number-ii
   @Language: C++
   @Datetime: 17-04-06 13:41
   */

// Method 1, DP, Time 27ms
class Solution {
public:
	/**
	 * @param n a positive integer
	 * @param primes the given prime list
	 * @return the nth super ugly number
	 * Tip: See problem ugly-number-ii
	 * */
	int nthSuperUglyNumber(int n, vector<int>& primes) {
		// Write your code here
		vector<long> dp(n,1);
		vector<int> pos(primes.size(),0);   //record last ugly pos by prime
		for(int i=1; i<n; ++i){
			long ugly = LONG_MAX;
			unordered_map<long,vector<int> > can;	// candidate ugly,pos
			for(int j=0; j<pos.size(); ++j){
				const long u = dp[pos[j]]*primes[j];
				if (ugly<u) continue;
				if (ugly=u) can[ugly].push_back(j);
				else can[ugly=u].push_back(j);
			}
			for(const auto &c : can[ugly])
				++pos[c];
			dp[i] = ugly;
		}
		return dp[n-1];
	}
};

// Method 2, Heap, Time 17ms
class Solution {
public:
	/**
	 * @param n a positive integer
	 * @param primes the given prime list
	 * @return the nth super ugly number
	 */
	int nthSuperUglyNumber(int n, vector<int>& primes) {
		typedef pair<long,int> UPI; // <ugly,primeid>
		priority_queue<UPI,vector<UPI>,greater<UPI> > minh;
		vector<long> dp(n,1);       // ugly numbers
		vector<int> pos(primes.size(),0), last(n,0);
		for(int i=0; i<primes.size(); ++i)
			minh.emplace(primes[i],i);
		for(int i=1; i<n; ++i){
			const auto upi = minh.top();
			minh.pop();
			dp[i] = upi.first;
			last[i] = upi.second;
			int k = upi.second;
			while(last[++pos[k]]>k);    // find nearest last ugly pos
			minh.emplace(dp[pos[k]]*primes[k],k);
		}
		return dp[n-1];
	}
};
